package from_0_to_50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q040 {
    static List<List<Integer>> lists;
    static List<Integer> list;
    static int[] candidates = new int[]{2,25,14,6,25,9,30,20,33,34,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12};
//    static int[] candidates = new int[]{1,2,1};
    static int target = 27; // 27

    public static void main(String[] args) {
        combinationSum2(candidates, target);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        lists = new ArrayList<>();
        list = new ArrayList<>();
        Arrays.sort(candidates);
        System.out.println(Arrays.toString(candidates));
//        dfs1(0, candidates, target);
        lists.forEach(list -> System.out.println(list.toString()));
        return lists;
    }

    public static void dfs(int startIndex, int[] candidates, int target) {
        if (list.size() == candidates.length) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (i > startIndex && candidates[i - 1] == candidates[i]) { // 行去重
                continue;
            } else {
                list.add(i);
                int sum = 0;
                for(int j = 0; j < list.size(); j++){
                    sum += candidates[list.get(j)];
                }
                if (sum == target) {
                    ArrayList<Integer> integers = new ArrayList<>();
                    for (int j = 0; j < list.size(); j++) {
                        integers.add(candidates[list.get(j)]);
                    }
                    lists.add(integers);
                }
                dfs(i + 1, candidates, target);
                list.remove(list.size() - 1);
            }
        }
    }
    public static void dfs1(int startIndex, int[] candidates, int target) {
        if (list.size() == candidates.length) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (i > startIndex && candidates[i - 1] == candidates[i]) { // 行去重
                continue;
            } else {
                list.add(candidates[i]);
                int sum = list.stream().mapToInt(t
                        -> t).sum();
                if (sum > target) {
                    list.remove(list.size() - 1);
                    return;
                }
                if (sum == target) {
                    System.out.println("list.toString() = " + list.toString());
                    lists.add(new ArrayList<>(list));
                }
                dfs1(i + 1, candidates, target);
                list.remove(list.size() - 1);
            }
        }
    }
}
